package leetcode_classic150;

public class Demo7 {



    // 289. 生命游戏
    private int n;
    private int m;
    public void gameOfLife(int[][] board) {
        // 模拟每个细胞状态变化
        n = board.length; m = board[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = judgeState(board, i, j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = res[i][j];
            }
        }
    }

    private final int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
    private final int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};
    private int judgeState(int[][] arr, int i, int j) {
        // 统计周围活细胞和死细胞的个数
        int exist = 0, die = 0;
        for (int k = 0; k < 8; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m) {
                if (arr[x][y] == 1) exist++;
                else die++;
            }
        }

        if (arr[i][j] == 1) {   // 活细胞
            if (exist < 2) return 0;
            if (exist <= 3) return 1;
        } else {                // 死细胞
            if (exist == 3) return 1;
        }
        return 0;
    }




    // 221. 最大正方形
    public int maximalSquare(char[][] matrix) {
        // dp[i][j]: 以 坐标(i, j) 为右下角的正方形的最大边长（正方形个数）
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n + 1][m + 1];

        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res * res;
    }



    // 1277. 统计全为 1 的正方形子矩阵
    public int countSquares(int[][] matrix) {
        // dp[i][j]: 以 坐标(i, j) 为右下角的正方形的最大边长（正方形个数）
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n + 1][m + 1];

        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (matrix[i - 1][j - 1] == 1) {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    res += dp[i][j];
                }
            }
        }
        return res;
    }
}
